package q78_subsets;

import java.util.ArrayList;
import java.util.List;

public class Solution_1 {

    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public static void main(String[] args) {

    }


    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums);
        return ans;
    }

    /**
     * 此题解的思路在于，对于数组里的每一个元素，都存在两种状态——被选择 未被选择
     * 所有的可能结合在一起，就得到了子集
     * 因此我们从数组的最开始设定子节点，每个子节点衍生出两条枝，一条是该节点被选择了进去，一条没有被选择进去
     * 一直到节点到达了nums的长度，所有的选择也就结束了
     */
    public void dfs(int cur, int[] nums) {
        // 如果cur到达了数组的长度，也就穷尽了最后一种可能，也就是所有的元素都被判断过了。
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        // 先将该节点加入到t中
        t.add(nums[cur]);
        dfs(cur + 1, nums);

        //另一种就是该节点没有被加入到t中
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }



}
